<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=yes">
<meta name="generator" content="litedown 0.7">
<title></title>
<style type="text/css">
body {
  font-family: sans-serif;
  max-width: 800px;
  margin: auto;
  padding: 1em;
  line-height: 1.5;
  print-color-adjust: exact;
  -webkit-print-color-adjust: exact;
}
body, .abstract, code, .footnotes, footer, #refs, .caption { font-size: .9em; }
li li { font-size: .95em; }
ul:has(li > input[type="checkbox"]) { list-style: none; padding-left: 1em; }
*, :before, :after { box-sizing: border-box; }
a { color: steelblue; }
pre, img { max-width: 100%; }
pre { white-space: pre-wrap; word-break: break-word; }
pre code { display: block; padding: 1em; overflow-x: auto; }
code { font-family: 'DejaVu Sans Mono', 'Droid Sans Mono', 'Lucida Console', Consolas, Monaco, monospace; }
:not(pre, th) > code, code[class], div > .caption { background: #f8f8f8; }
pre > code:is(:not([class]), .language-plain, .language-none, .plain), .box, .figure, .table { background: inherit; border: 1px solid #eee; }
pre > code {
  &.message { border-color: #9eeaf9; }
  &.warning { background: #fff3cd; border-color: #fff3cd; }
  &.error { background: #f8d7da; border-color: #f8d7da; }
}
.fenced-chunk { border-left: 1px solid #666; }
.code-fence {
  opacity: .4;
  border: 1px dashed #666;
  border-left: 2px solid;
  &:hover { opacity: inherit; }
}
.box, .figure, .table, table { margin: 1em auto; }
div > .caption { padding: 1px 1em; }
.figure { p:has(img, svg), pre:has(svg) { text-align: center; } }
.flex-col { display: flex; justify-content: space-between; }
table {
  &:only-child:not(.table > *) { margin: auto; }
  th, td { padding: 5px; font-variant-numeric: tabular-nums; }
  thead, tfoot, tr:nth-child(even) { background: whitesmoke; }
  thead th { border-bottom: 1px solid #ddd; }
  &:not(.datatable-table) {
    border-top: 1px solid #666;
    border-bottom: 1px solid #666;
  }
}
blockquote {
  color: #666;
  margin: 0;
  padding: 1px 1em;
  border-left: .5em solid #eee;
}
hr, .footnotes::before { border: 1px dashed #ddd; }
.frontmatter { text-align: center; }
#TOC {
  a { text-decoration: none; }
  ul { list-style: none; padding-left: 1em; }
  & > ul { padding: 0; }
  ul ul { border-left: 1px solid lightsteelblue; }
}
.body h2 { border-bottom: 1px solid #666; }
.body .appendix, .appendix ~ h2 { border-bottom-style: dashed; }
.main-number::after { content: "."; }
span[class^="ref-number-"] { font-weight: bold; }
.ref-number-fig::after, .ref-number-tab::after { content: ":"; }
.cross-ref-chp::before { content: "Chapter "; }
.cross-ref-sec::before { content: "Section "; }
.cross-ref-fig::before, .ref-number-fig::before { content: "Figure "; }
.cross-ref-tab::before, .ref-number-tab::before { content: "Table "; }
.cross-ref-eqn::before, .MathJax_ref:has(mjx-mtext > mjx-c + mjx-c)::before { content: "Equation "; }
.abstract, #refs {
  &::before { display: block; margin: 1em auto; font-weight: bold; }
}
.abstract::before { content: "Abstract"; text-align: center; }
#refs::before { content: "Bibliography"; font-size: 1.5em; }
.ref-paren-open::before { content: "("; }
.ref-paren-close::after { content: ")"; }
.ref-semicolon::after { content: "; "; }
.ref-and::after { content: " and "; }
.ref-et-al::after { content: " et al."; font-style: italic; }
.footnote-ref a {
  &::before { content: "["; }
  &::after { content: "]"; }
}
section.footnotes {
  margin-top: 2em;
  &::before { content: ""; display: block; max-width: 20em; }
}
.fade {
  background: repeating-linear-gradient(135deg, white, white 30px, #ddd 32px, #ddd 32px);
  opacity: 0.6;
}

@media print {
  body { max-width: 100%; }
  tr, img { break-inside: avoid; }
}
@media only screen and (min-width: 992px) {
  body:not(.pagesjs) pre:has(.line-numbers):not(:hover) { white-space: pre; }
}
</style>
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@xiee/utils@1.14.14/css/prism-xcode.min.css">
<script src="https://cdn.jsdelivr.net/npm/prismjs@1.29.0/components/prism-core.min.js" defer></script>
<script src="https://cdn.jsdelivr.net/npm/prismjs@1.29.0/plugins/autoloader/prism-autoloader.min.js" defer></script>
</head>
<body>
<div class="frontmatter">
</div>
<div class="body">
<pre><code class="language-r"># Breadth-First Search (BFS) Algorithm
#
# BFS is a graph traversal algorithm that explores all vertices at the current depth
# before moving to vertices at the next depth level. It uses a queue data structure.
#
# Time Complexity: O(V + E) where V is vertices and E is edges
# Space Complexity: O(V) for the visited array and queue
#
# Input: An adjacency list representation of a graph and a starting vertex
# Output: The order in which vertices are visited during BFS traversal

# BFS function using queue (implemented with vector)
breadth_first_search &lt;- function(graph, start_vertex) {
  # Get all vertices in the graph
  all_vertices &lt;- unique(c(names(graph), unlist(graph)))
  
  # Initialize visited array and queue
  visited &lt;- rep(FALSE, max(all_vertices))
  names(visited) &lt;- 1:max(all_vertices)
  queue &lt;- c(start_vertex)
  result &lt;- c()
  
  # Mark starting vertex as visited
  visited[start_vertex] &lt;- TRUE
  
  while (length(queue) &gt; 0) {
    # Dequeue vertex from front of queue
    vertex &lt;- queue[1]
    queue &lt;- queue[-1]
    result &lt;- c(result, vertex)
    
    # Add all unvisited neighbors to queue
    if (as.character(vertex) %in% names(graph)) {
      for (neighbor in graph[[as.character(vertex)]]) {
        if (!visited[neighbor]) {
          visited[neighbor] &lt;- TRUE
          queue &lt;- c(queue, neighbor)
        }
      }
    }
  }
  
  return(result)
}

# BFS to find shortest path between two vertices
bfs_shortest_path &lt;- function(graph, start_vertex, end_vertex) {
  # Get all vertices in the graph
  all_vertices &lt;- unique(c(names(graph), unlist(graph)))
  
  # Initialize visited array, queue, and parent tracking
  visited &lt;- rep(FALSE, max(all_vertices))
  names(visited) &lt;- 1:max(all_vertices)
  parent &lt;- rep(-1, max(all_vertices))
  names(parent) &lt;- 1:max(all_vertices)
  queue &lt;- c(start_vertex)
  
  # Mark starting vertex as visited
  visited[start_vertex] &lt;- TRUE
  
  while (length(queue) &gt; 0) {
    # Dequeue vertex from front of queue
    vertex &lt;- queue[1]
    queue &lt;- queue[-1]
    
    # If we reached the target vertex, reconstruct path
    if (vertex == end_vertex) {
      path &lt;- c()
      current &lt;- end_vertex
      
      # Backtrack using parent array
      while (current != -1) {
        path &lt;- c(current, path)
        current &lt;- parent[current]
      }
      
      return(list(
        path = path,
        distance = length(path) - 1
      ))
    }
    
    # Add all unvisited neighbors to queue
    if (as.character(vertex) %in% names(graph)) {
      for (neighbor in graph[[as.character(vertex)]]) {
        if (!visited[neighbor]) {
          visited[neighbor] &lt;- TRUE
          parent[neighbor] &lt;- vertex
          queue &lt;- c(queue, neighbor)
        }
      }
    }
  }
  
  # No path found
  return(list(
    path = NULL,
    distance = -1
  ))
}

# BFS to find all vertices at a specific distance
bfs_vertices_at_distance &lt;- function(graph, start_vertex, target_distance) {
  # Get all vertices in the graph
  all_vertices &lt;- unique(c(names(graph), unlist(graph)))
  
  # Initialize visited array, queue with distances
  visited &lt;- rep(FALSE, max(all_vertices))
  names(visited) &lt;- 1:max(all_vertices)
  queue &lt;- list(list(vertex = start_vertex, distance = 0))
  vertices_at_distance &lt;- c()
  
  # Mark starting vertex as visited
  visited[start_vertex] &lt;- TRUE
  
  while (length(queue) &gt; 0) {
    # Dequeue vertex with distance from front of queue
    current &lt;- queue[[1]]
    queue &lt;- queue[-1]
    vertex &lt;- current$vertex
    distance &lt;- current$distance
    
    # If current distance matches target, add to result
    if (distance == target_distance) {
      vertices_at_distance &lt;- c(vertices_at_distance, vertex)
    }
    
    # Don't explore further if we've reached target distance
    if (distance &lt; target_distance) {
      # Add all unvisited neighbors to queue
      if (as.character(vertex) %in% names(graph)) {
        for (neighbor in graph[[as.character(vertex)]]) {
          if (!visited[neighbor]) {
            visited[neighbor] &lt;- TRUE
            queue &lt;- c(queue, list(list(vertex = neighbor, distance = distance + 1)))
          }
        }
      }
    }
  }
  
  return(vertices_at_distance)
}

# Example usage and testing
cat(&quot;=== Breadth-First Search (BFS) Algorithm ===\n&quot;)
</code></pre>
<pre><code>## === Breadth-First Search (BFS) Algorithm ===
</code></pre>
<pre><code class="language-r"># Create a sample graph as adjacency list
# Graph structure:
#     1
#    / \
#   2   3
#  / \   \
# 4   5   6
graph &lt;- list(
  &quot;1&quot; = c(2, 3),
  &quot;2&quot; = c(4, 5),
  &quot;3&quot; = c(6),
  &quot;4&quot; = c(),
  &quot;5&quot; = c(),
  &quot;6&quot; = c()
)

cat(&quot;Graph structure (adjacency list):\n&quot;)
</code></pre>
<pre><code>## Graph structure (adjacency list):
</code></pre>
<pre><code class="language-r">for (vertex in names(graph)) {
  cat(&quot;Vertex&quot;, vertex, &quot;-&gt; [&quot;, paste(graph[[vertex]], collapse = &quot;, &quot;), &quot;]\n&quot;)
}
</code></pre>
<pre><code>## Vertex 1 -&gt; [ 2, 3 ]
## Vertex 2 -&gt; [ 4, 5 ]
## Vertex 3 -&gt; [ 6 ]
## Vertex 4 -&gt; [  ]
## Vertex 5 -&gt; [  ]
## Vertex 6 -&gt; [  ]
</code></pre>
<pre><code class="language-r"># Test BFS traversal
cat(&quot;\nBFS starting from vertex 1:\n&quot;)
</code></pre>
<pre><code>## 
## BFS starting from vertex 1:
</code></pre>
<pre><code class="language-r">result &lt;- breadth_first_search(graph, 1)
cat(&quot;Traversal order:&quot;, paste(result, collapse = &quot; -&gt; &quot;), &quot;\n&quot;)
</code></pre>
<pre><code>## Traversal order: 1 -&gt; 2 -&gt; 3 -&gt; 4 -&gt; 5 -&gt; 6
</code></pre>
<pre><code class="language-r"># Test BFS from different starting vertex
cat(&quot;\nBFS starting from vertex 2:\n&quot;)
</code></pre>
<pre><code>## 
## BFS starting from vertex 2:
</code></pre>
<pre><code class="language-r">result_from_2 &lt;- breadth_first_search(graph, 2)
cat(&quot;Traversal order:&quot;, paste(result_from_2, collapse = &quot; -&gt; &quot;), &quot;\n&quot;)
</code></pre>
<pre><code>## Traversal order: 2 -&gt; 4 -&gt; 5
</code></pre>
<pre><code class="language-r"># Test shortest path finding
cat(&quot;\n=== Shortest Path Finding ===\n&quot;)
</code></pre>
<pre><code>## 
## === Shortest Path Finding ===
</code></pre>
<pre><code class="language-r">path_result &lt;- bfs_shortest_path(graph, 1, 5)
if (!is.null(path_result$path)) {
  cat(&quot;Shortest path from 1 to 5:&quot;, paste(path_result$path, collapse = &quot; -&gt; &quot;), &quot;\n&quot;)
  cat(&quot;Distance:&quot;, path_result$distance, &quot;\n&quot;)
} else {
  cat(&quot;No path found from 1 to 5\n&quot;)
}
</code></pre>
<pre><code>## Shortest path from 1 to 5: 1 -&gt; 2 -&gt; 5 
## Distance: 2
</code></pre>
<pre><code class="language-r"># Test vertices at specific distance
cat(&quot;\n=== Vertices at Specific Distance ===\n&quot;)
</code></pre>
<pre><code>## 
## === Vertices at Specific Distance ===
</code></pre>
<pre><code class="language-r">vertices_dist_2 &lt;- bfs_vertices_at_distance(graph, 1, 2)
cat(&quot;Vertices at distance 2 from vertex 1:&quot;, paste(vertices_dist_2, collapse = &quot;, &quot;), &quot;\n&quot;)
</code></pre>
<pre><code>## Vertices at distance 2 from vertex 1: 4, 5, 6
</code></pre>
<pre><code class="language-r"># Example with a more complex connected graph
cat(&quot;\n=== Example with More Complex Graph ===\n&quot;)
</code></pre>
<pre><code>## 
## === Example with More Complex Graph ===
</code></pre>
<pre><code class="language-r">complex_graph &lt;- list(
  &quot;1&quot; = c(2, 3),
  &quot;2&quot; = c(1, 4, 5),
  &quot;3&quot; = c(1, 6),
  &quot;4&quot; = c(2, 7),
  &quot;5&quot; = c(2, 8),
  &quot;6&quot; = c(3, 9),
  &quot;7&quot; = c(4),
  &quot;8&quot; = c(5),
  &quot;9&quot; = c(6)
)

cat(&quot;Complex graph BFS starting from vertex 1:\n&quot;)
</code></pre>
<pre><code>## Complex graph BFS starting from vertex 1:
</code></pre>
<pre><code class="language-r">complex_result &lt;- breadth_first_search(complex_graph, 1)
cat(&quot;Traversal order:&quot;, paste(complex_result, collapse = &quot; -&gt; &quot;), &quot;\n&quot;)
</code></pre>
<pre><code>## Traversal order: 1 -&gt; 2 -&gt; 3 -&gt; 4 -&gt; 5 -&gt; 6 -&gt; 7 -&gt; 8 -&gt; 9
</code></pre>
<pre><code class="language-r"># Test shortest path in complex graph
path_complex &lt;- bfs_shortest_path(complex_graph, 1, 9)
if (!is.null(path_complex$path)) {
  cat(&quot;Shortest path from 1 to 9:&quot;, paste(path_complex$path, collapse = &quot; -&gt; &quot;), &quot;\n&quot;)
  cat(&quot;Distance:&quot;, path_complex$distance, &quot;\n&quot;)
}
</code></pre>
<pre><code>## Shortest path from 1 to 9: 1 -&gt; 3 -&gt; 6 -&gt; 9 
## Distance: 3
</code></pre>
</div>
</body>
</html>
